home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / c / bisonpcb.zip / CONFLICT.C < prev    next >
C/C++ Source or Header  |  1987-02-13  |  15KB  |  727 lines
  1. /* Find and resolve or report look-ahead conflicts for bison,
  2.    Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
  3.   
  4. BISON is distributed in the hope that it will be useful, but WITHOUT ANY
  5. WARRANTY.  No author or distributor accepts responsibility to anyone
  6. for the consequences of using it or for whether it serves any
  7. particular purpose or works at all, unless he says so in writing.
  8. Refer to the BISON General Public License for full details.
  9.   
  10. Everyone is granted permission to copy, modify and redistribute BISON,
  11. but only under the conditions described in the BISON General Public
  12. License.  A copy of this license is supposed to have been given to you
  13. along with BISON so you can know your rights and responsibilities.  It
  14. should be in a file named COPYING.  Among other things, the copyright
  15. notice and this notice must be preserved on all copies.
  16.   
  17.  In other words, you are welcome to use, share and improve this program.
  18.  You are forbidden to forbid anyone else to use, share and improve
  19.  what you give them.   Help stamp out software-hoarding!  */
  20.  
  21. /*
  22.  * Port to PC by Whit Gregg
  23.  *               Nourse, Gregg & Browne, Inc.
  24.  *         1 Horizon Road
  25.  *         Fort Lee, NJ  07024
  26.  */
  27.  
  28.  
  29. #include <stdio.h>
  30. #include <malloc.h>
  31. #include <memory.h>
  32. #include "machine.h"
  33. #include "new.h"
  34. #include "files.h"
  35. #include "gram.h"
  36. #include "state.h"
  37. #include "func.h"
  38.  
  39.  
  40.     extern char **tags;
  41. extern int tokensetsize;
  42. extern char *consistent;
  43. extern short *accessing_symbol;
  44. extern shifts **shift_table;
  45. extern unsigned *LA;
  46. extern short *LAruleno;
  47. extern short *lookaheads;
  48. extern int verboseflag;
  49.  
  50. char any_conflicts;
  51. char *conflicts;
  52. errs **err_table;
  53.  
  54.  
  55. static unsigned *shiftset;
  56. static unsigned *lookaheadset;
  57. static int src_total;
  58. static int rrc_total;
  59. static int src_count;
  60. static int rrc_count;
  61.  
  62.  
  63.  
  64. void 
  65. initialize_conflicts()
  66. {                /* WG */
  67.     register int i;
  68.  
  69. /*  register errs *sp; JF unused */
  70.  
  71.     conflicts = NEW2(nstates, char);
  72.     shiftset = NEW2(tokensetsize, unsigned);
  73.     lookaheadset = NEW2(tokensetsize, unsigned);
  74.  
  75.     err_table = NEW2(nstates, errs *);
  76.  
  77.     any_conflicts = 0;
  78.  
  79.     for (i = 0; i < nstates; i++)
  80.         set_conflicts(i);
  81.     }
  82.  
  83.  
  84.  
  85. void 
  86. set_conflicts(state)        /* WG */
  87.     int state;
  88. {
  89.     register int i;
  90.     register int k;
  91.     register shifts *shiftp;
  92.     register unsigned *fp2;
  93.     register unsigned *fp3;
  94.     register unsigned *fp4;
  95.     register unsigned *fp1;
  96.     register int symbol;
  97.  
  98.     if (consistent[state])
  99.         return;
  100.  
  101.     for (i = 0; i < tokensetsize; i++)
  102.         lookaheadset[i] = 0;
  103.  
  104.     shiftp = shift_table[state];
  105.     if (shiftp) {
  106.         k = shiftp->nshifts;
  107.         for (i = 0; i < k; i++) {
  108.             symbol = accessing_symbol[shiftp->shifts[i]];
  109.             if (ISVAR(symbol))
  110.                 break;
  111.             SETBIT(lookaheadset, symbol);
  112.             }
  113.         }
  114.  
  115.     k = lookaheads[state + 1];
  116.     fp4 = lookaheadset + tokensetsize;
  117.  
  118.     /* loop over all rules which require lookahead in this state */
  119.     /*
  120.      * first check for shift-reduce conflict, and try to resolve using
  121.      * precedence  
  122.      */
  123.  
  124.     for (i = lookaheads[state]; i < k; i++)
  125.         if (rprec[LAruleno[i]]) {
  126.             fp1 = LA + i * tokensetsize;
  127.             fp2 = fp1;
  128.             fp3 = lookaheadset;
  129.  
  130.             while (fp3 < fp4) {
  131.                 if (*fp2++ & *fp3++) {
  132.                     resolve_sr_conflict(state, i);
  133.                     break;
  134.                     }
  135.                 }
  136.             }
  137.  
  138.     /* loop over all rules which require lookahead in this state */
  139.     /* Check for conflicts not resolved above.  */
  140.  
  141.     for (i = lookaheads[state]; i < k; i++) {
  142.         fp1 = LA + i * tokensetsize;
  143.         fp2 = fp1;
  144.         fp3 = lookaheadset;
  145.  
  146.         while (fp3 < fp4) {
  147.             if (*fp2++ & *fp3++) {
  148.                 conflicts[state] = 1;
  149.                 any_conflicts = 1;
  150.                 }
  151.             }
  152.  
  153.         fp2 = fp1;
  154.         fp3 = lookaheadset;
  155.  
  156.         while (fp3 < fp4)
  157.             *fp3++ |= *fp2++;
  158.         }
  159.     }
  160.  
  161.  
  162.  
  163. /* Attempt to resolve shift-reduce conflict for one rule
  164. by means of precedence declarations.
  165. It has already been checked that the rule has a precedence.
  166. A conflict is resolved by modifying the shift or reduce tables
  167. so that there is no longer a conflict.  */
  168.  
  169. void 
  170. resolve_sr_conflict(state, lookaheadnum)    /* WG */
  171.     int state;
  172.     int lookaheadnum;
  173. {
  174.     register int i;
  175.     register int mask;
  176.     register unsigned *fp1;
  177.     register unsigned *fp2;
  178.     register int redprec;
  179.     errs *errp = (errs *) alloca(sizeof(errs) + ntokens * sizeof(short));
  180.     short *errtokens = errp->errs;
  181.  
  182.     /* find the rule to reduce by to get precedence of reduction  */
  183.     redprec = rprec[LAruleno[lookaheadnum]];
  184.  
  185.     mask = 1;
  186.     fp1 = LA + lookaheadnum * tokensetsize;
  187.     fp2 = lookaheadset;
  188.     for (i = 0; i < ntokens; i++) {
  189.         if ((mask & *fp2 & *fp1) && sprec[i])
  190.             /*
  191.              * shift-reduce conflict occurs for token number i
  192.              * and it has a precision. The precedence of shifting
  193.              * is that of token i.  
  194.              */
  195.         {
  196.             if (sprec[i] < redprec) {
  197.                 if (verboseflag)
  198.                     log_resolution(state, lookaheadnum, i, "reduce");
  199.                 *fp2 &= ~mask;    /* flush the shift for this
  200.                          * token */
  201.                 flush_shift(state, i);
  202.                 }
  203.             else if (sprec[i] > redprec) {
  204.                 if (verboseflag)
  205.                     log_resolution(state, lookaheadnum, i, "shift");
  206.                 *fp1 &= ~mask;    /* flush the reduce for this
  207.                          * token */
  208.                 }
  209.             else {
  210.                 /*
  211.                  * Matching precedence levels. For left
  212.                  * association, keep only the reduction. For
  213.                  * right association, keep only the shift.
  214.                  * For nonassociation, keep neither.  
  215.                  */
  216.  
  217.                 switch (sassoc[i]) {
  218.  
  219.                     case RIGHT_ASSOC:
  220.                     if (verboseflag)
  221.                         log_resolution(state, lookaheadnum, i, "shift");
  222.                     break;
  223.  
  224.                     case LEFT_ASSOC:
  225.                     if (verboseflag)
  226.                         log_resolution(state, lookaheadnum, i, "reduce");
  227.                     break;
  228.  
  229.                     case NON_ASSOC:
  230.                     if (verboseflag)
  231.                         log_resolution(state, lookaheadnum, i, "an error");
  232.                     break;
  233.                     }
  234.  
  235.                 if (sassoc[i] != RIGHT_ASSOC) {
  236.                     *fp2 &= ~mask;    /* flush the shift for
  237.                              * this token */
  238.                     flush_shift(state, i);
  239.                     }
  240.                 if (sassoc[i] != LEFT_ASSOC) {
  241.                     *fp1 &= ~mask;    /* flush the reduce for
  242.                              * this token */
  243.                     }
  244.                 if (sassoc[i] == NON_ASSOC) {
  245.                     /*
  246.                      * Record an explicit error for this
  247.                      * token.  
  248.                      */
  249.                     *errtokens++ = i;
  250.                     }
  251.                 }
  252.             }
  253.  
  254.         mask <<= 1;
  255.         if (mask == 0) {
  256.             mask = 1;
  257.             fp2++;
  258.             fp1++;
  259.             }
  260.         }
  261.     errp->nerrs = errtokens - errp->errs;
  262.     if (errp->nerrs) {
  263.         /*
  264.          * Some tokens have been explicitly made errors.  Allocate a
  265.          * permanent errs structure for this state, to record them.  
  266.          */
  267.         i = (char *) errtokens - (char *) errp;
  268.         err_table[state] = (errs *) allocate((unsigned int) i);
  269.         /* bcopy (errp, err_table[state], i); *//* WG */
  270.         memcpy((char *) err_table[state], (char *) errp, i);    /* WG */
  271.         }
  272.     else
  273.         err_table[state] = 0;
  274.     }
  275.  
  276.  
  277.  
  278. /* turn off the shift recorded for the specified token in the specified state.
  279. Used when we resolve a shift-reduce conflict in favor of the reduction.  */
  280.  
  281. void 
  282. flush_shift(state, token)    /* WG */
  283.     int state;
  284.     int token;
  285. {
  286.     register shifts *shiftp;
  287.     register int k, i;
  288.  
  289. /*  register unsigned symbol; JF unused */
  290.  
  291.     shiftp = shift_table[state];
  292.  
  293.     if (shiftp) {
  294.         k = shiftp->nshifts;
  295.         for (i = 0; i < k; i++) {
  296.             if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
  297.                 (shiftp->shifts[i]) = 0;
  298.             }
  299.         }
  300.     }
  301.  
  302.  
  303.  
  304. void 
  305. log_resolution(state, LAno, token, resolution)    /* WG */
  306.     int state, LAno, token;
  307.     char *resolution;
  308. {
  309.     fprintf(foutput,
  310.         "Conflict in state %d between rule %d and token %s resolved as %s.\n",
  311.         state, LAruleno[LAno], tags[token], resolution);
  312.     }
  313.  
  314.  
  315.  
  316. void 
  317. conflict_log()
  318. {                /* WG */
  319.     register int i;
  320.  
  321.     src_total = 0;
  322.     rrc_total = 0;
  323.  
  324.     for (i = 0; i < nstates; i++) {
  325.         if (conflicts[i]) {
  326.             count_sr_conflicts(i);
  327.             count_rr_conflicts(i);
  328.             src_total += src_count;
  329.             rrc_total += rrc_count;
  330.             }
  331.         }
  332.  
  333.     total_conflicts();
  334.     }
  335.  
  336.  
  337.  
  338. void 
  339. verbose_conflict_log()
  340. {                /* WG */
  341.     register int i;
  342.  
  343.     src_total = 0;
  344.     rrc_total = 0;
  345.  
  346.     for (i = 0; i < nstates; i++) {
  347.         if (conflicts[i]) {
  348.             count_sr_conflicts(i);
  349.             count_rr_conflicts(i);
  350.             src_total += src_count;
  351.             rrc_total += rrc_count;
  352.  
  353.             fprintf(foutput, "State %d contains